Exponential smoothing is a form of statistical summary gathering that takes a previous period's summary and adjusts it up or down based on what actually occurred in that period. This is carried out by calculating a weighted moving average of the two values.
In computer system technology, it is often required to keep track of some smoothed usage/frequency statistic on a set of objects. For example, such techniques are useful in caching, scheduling, and data compression. As a specific example, there may be activity on a plurality of queues and it may be advantageous to monitor and determine the relative activity of the queues in order to allocate resources such as processor time or memory capacity. Maintaining a history of the activity in a time period for analysis requires a high level of processor and storage capacity. Therefore, a statistical summary method is used to adapt a summary based on the activity.
In the following description, the notation { } (as in v{t}) is used herein to indicate the value of a variable v at time t. In an implementation, these values will be simple variables that are overwritten as time progresses.
Similarly, the notation [ ] (as in S[i]) is used to indicate multiple values stored at once and discriminated by [i], possibly in an array or possibly in some other mechanism. For example, if S[i] indicates activity on a queue, then [i] will represent each queue: the s data may be stored as a field in each queue.
Exponential smoothing provides a common and cheap way to smooth a single statistic. For example, when new value v{t} arrives at time t, the smoothed value S {t} is changed by using the following formula: S{t}=k*s{t−1}+(1−k)*v{t}where k is a weighting factor between 0 and 1, typically in range 0.9 to 0.999. Formula 1
The smoothed value S {t} is the summary value at time t. This is equal to the smoothed value S{t−1} at the previous time t−1 multiplied by the weighting factor k, plus the actual value at time t multiplied by 1−k.
There are variations to this formula but the principle remains the same. For example, variations include whether elapsed time between events is allowed for and whether an event has a ‘value’.
In the applications of caching, scheduling or data compression, there is a set of statistics to maintain. For example, the set of statistics may be for objects [1], [2], etc, or queues [myQueue], [hisQueue], etc. Typically, relative values are of interest. Thus, to keep all relative values in sync, when event value v[i]{t} arrives for object [i] at time t, the formula for exponential smoothing can be written as follows:S[i]{t}=k*S[i]{t−1}+(1−k)*v[i]{t}S[j]{t}=k*S[j]{t−1} for all objects [j] where j!=i(j does not equal i)  Formula 2
Using the example of the queues, if there is an event on queue [i], the summary for the queue will change by an exponential increase as there is an increase in the probability of activity on queue [i]. All the other queues [j] will have their summary changed by a corresponding exponential decay, as there is a decrease in the probability of activity on these other queues [i].
The cost of the update to S[j] for all other objects on which an event has not occurred is clearly undesirable. There may be a high number of objects and the update of the summary for each of the objects limits the scalability of the statistical summary method. This can be mitigated by careful coding, but it remains a problem.
Applying exponential smoothing to large quantities of data results in a very high number of calculations that are not necessary until the time when an actual metric is required. It is an aim of the present invention to reduce the number of calculations required while providing an exponential smoothing technique.